import java.util.*;

public class Test {

    // 题目1 ：图像渲染
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color){
            return image;
        }

        int prev = image[sr][sc];

        int m = image.length;
        int n = image[0].length;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sr, sc});
        image[sr][sc] = color;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int i = 0; i < 4; i++){
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){
                    q.offer(new int[]{x, y});
                    image[x][y] = color;
                }
            }
        }
        return image;
    }

    // 题目2：岛屿数量
    int m, n;
    boolean[][] vis;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        int ret = 0 ;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1' && !vis[i][j]){
                    BFS(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }

    public void BFS(char[][] grid, int i, int j){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        vis[i][j] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k] , y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]){
                    q.offer(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
    }

    // 题目3：装满杯子需要的最短总时长
    public int fillCups(int[] amount) {
        insertSort(amount);
        return amount[0] + amount[1] <= amount[2] ? amount[2] : (amount[0] + amount[1] + amount[2] + 1) / 2;
    }

    public void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int j = i - 1;
            int temp = arr[i];
            for(; j >= 0; j--){
                if(arr[j] > arr[j + 1]){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + 1] = temp;
        }
    }

    // 题目4：数组中两元素的最大乘积
    public int maxProduct(int[] nums) {
        gapChoose(nums);
        return (nums[0] - 1) * (nums[1] - 1);
    }

    public void gapChoose(int[] arr){
        int gap = arr.length;
        while(gap >= 1){
            shellSort(arr, gap);
            gap /= 2;
        }
    }

    public void shellSort(int[] arr, int gap){
        for(int i = gap; i < arr.length; i++){
            int j = i - gap;
            int temp = arr[i];
            for(;j >= 0; j -= gap){
                if(temp > arr[j]){
                    arr[j + gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }

    //题目5： 岛屿的面积
    int max ;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        vis = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1 && !vis[i][j]){
                    max = Math.max(max, BFS(grid, i, j));
                }
            }
        }
        return max;
    }

    public int BFS(int[][] grid, int i, int j){
        int area = 1;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        vis[i][j] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k] , y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){
                    q.offer(new int[]{x, y});
                    vis[x][y] = true;
                    area++;
                }
            }
        }
        return area;
    }

    // 题目6：被围绕的区域

//    boolean[][] vis;
//    int[] dx = {0, 0, 1, -1};
//    int[] dy = {1, -1, 0, 0};
//    int m, n;
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        vis = new boolean[m][n];

        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O')
                BFS1(board, i, 0);
            if(board[i][n - 1] == 'O')
                BFS1(board, i, n - 1);
        }

        for(int i = 0; i < n; i++){
            if(board[0][i] == 'O')
                BFS1(board, 0, i);
            if(board[m - 1][i] == 'O')
                BFS1(board, m - 1, i);
        }

        for(int i = 1; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                if(board[i][j] == 'O' && !vis[i][j]){
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void BFS1(char[][] board, int i, int j){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        vis[i][j] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !vis[x][y]){
                    q.offer(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
    }


    // 还可以改成 ‘.’
    public void solve1(char[][] board) {
        m = board.length;
        n = board[0].length;

        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O')
                BFS2(board, i, 0);
            if(board[i][n - 1] == 'O')
                BFS2(board, i, n - 1);
        }

        for(int i = 0; i < n; i++){
            if(board[0][i] == 'O')
                BFS2(board, 0, i);
            if(board[m - 1][i] == 'O')
                BFS2(board, m - 1, i);
        }

        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == '.'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void BFS2(char[][] board, int i, int j){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        board[i][j] = '.';
        while(!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' ){
                    q.offer(new int[]{x, y});
                    board[x][y] = '.';
                }
            }
        }
    }

    // 题目 7 ： 迷宫中离入口最近的出口
//    boolean[][] vis;
//    int[] dx = {0, 0, 1, -1};
//    int[] dy = {1, -1, 0, 0};
    public int nearestExit(char[][] maze, int[] e) {
        int m = maze.length;
        int n = maze[0].length;
        vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{e[0], e[1]});
        vis[e[0]][e[1]] = true;
        int step = 0;
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            for(int i = 0; i < sz; i++){
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for(int k = 0; k < 4; k++){
                    int x = a + dx[k] , y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.'){
                        if(x == 0 || x == m - 1 || y == 0 || y == n - 1  ){
                            return step;
                        }
                        q.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
    

}
